package com.kehao.newcoder;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class NC92Solution {
    public String LCS (String s1, String s2) {
        int m = s1.length()+1;
        int n = s2.length()+1;
        int[][] dp =  new int[m][n];
        int[][][] pos = new int[m][n][];
        dp[0][0] = 0;
        for (int i = 1; i < m; i++) {
            dp[i][0] = 0;
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    pos[i][j] = new int[]{-1,i-1,j-1};
                }else if(dp[i][j-1]>dp[i-1][j]){
                    dp[i][j] = dp[i][j-1];
                    pos[i][j] = new int[]{1,i,j-1};
                }else {
                    dp[i][j] = dp[i-1][j];
                    pos[i][j] = new int[]{1,i-1,j};
                }
            }
        }
        List<Character> list = new ArrayList<>();
        int[] p = pos[m-1][n-1];
        while (p!=null){
            if(p[0]==-1){
                list.add(s1.charAt(p[1]));
            }
            p = pos[p[1]][p[2]];
        }
        StringBuffer sb = new StringBuffer();
        for (int i = list.size()-1;i>=0;i--) {
            sb.append(list.get(i));
        }
        String result = sb.toString();
        if(result.equals("")){
            return "-1";
        }else {
            return result;
        }
    }

    @Test
    public void test01(){
        String s1 = "1A2C3D4B56",s2 ="B1D23A456A";
        System.out.println(LCS(s1, s2));
    }
}
